<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Computes a minimum-perimeter bounding box subject to positioning constraints</title>
<link rel="canonical" href="/Users/mcgrant/Repos/CVX/examples/cvxbook/Ch08_geometric_probs/html/floorplan.html">
<link rel="stylesheet" href="../../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Computes a minimum-perimeter bounding box subject to positioning constraints</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
Text output
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="keyword">function</span> [W, H, w, h, x, y] = floorplan(adj_H, adj_V, rho, Amin, l, u )

<span class="comment">% Inputs:</span>
<span class="comment">%      adj_H,adj_V: adjacency matrices</span>
<span class="comment">%      Amin:        minimum spacing: w_i * h_i &gt;= Amin</span>
<span class="comment">%      rho:         boundaries: rho &lt;= x_i &lt;= W-rho, rho &lt;= y_i &lt;= H-rho</span>
<span class="comment">%      l, u:        aspect ratio constraints: l_i &lt;= h_i/w_i &lt;= u_i</span>
<span class="comment">% Only adj_H and adj_V are required; the rest are optional. If n is the</span>
<span class="comment">% number of cells, then adj_H and adj_V must be nxn matrices, and Amin,</span>
<span class="comment">% l, and u must be vectors of length n. rho must be a scalar. The default</span>
<span class="comment">% values of rho and Amin are 0.</span>
<span class="comment">% Joelle Skaf - 12/04/05</span>

<span class="keyword">if</span> nargin &lt; 2
    error(<span class="string">'Insufficient number of input arguments'</span>);
<span class="keyword">end</span>

[n1, n2] = size(adj_H);
[m1, m2] = size(adj_V);

<span class="keyword">if</span> n1~=n2
    error(<span class="string">'Input adjacency matrix for horizontal graph must be square'</span>);
<span class="keyword">end</span>

<span class="keyword">if</span> m1~=m2
    error(<span class="string">'Input adjacency matrix for horizontal graph must be square'</span>);
<span class="keyword">end</span>


<span class="keyword">if</span> n1~=m1
    error(<span class="string">'Input adjacency matrices must be of the same size'</span>);
<span class="keyword">end</span>

n = n1;                     <span class="comment">% number of cells</span>

<span class="keyword">if</span> nargin &lt;3
    rho = 0;
<span class="keyword">end</span>

<span class="keyword">if</span> nargin &lt;4
    Amin = zeros(1,n);
<span class="keyword">else</span>
    <span class="keyword">if</span> min(size(Amin)) ~=1
        error(<span class="string">'Amin should be a vector'</span>);
    <span class="keyword">end</span>
    <span class="keyword">if</span> max(size(Amin)) ~= n
        error(<span class="string">'Amin should have the same length as the input graphs'</span>);
    <span class="keyword">end</span>
    <span class="keyword">if</span> size(Amin,1)~=1
        Amin = Amin';
    <span class="keyword">end</span>
<span class="keyword">end</span>

<span class="keyword">if</span> nargin == 5
    <span class="keyword">if</span> min(size(1)) ~= 1
        error(<span class="string">'l must be a vector'</span>);
    <span class="keyword">end</span>
    <span class="keyword">if</span> max(size(l)) ~= n
        error(<span class="string">'the vector l must have same length as the input graphs'</span>);
    <span class="keyword">end</span>
    <span class="keyword">if</span> size(l,1) == 1
        l = l';
    <span class="keyword">end</span>
<span class="keyword">end</span>

<span class="keyword">if</span> nargin == 6
    <span class="keyword">if</span> min(size(1)) ~= 1
        error(<span class="string">'u must be a vector'</span>);
    <span class="keyword">end</span>
    <span class="keyword">if</span> max(size(u)) ~= n
        error(<span class="string">'the vector u must have same length as the input graphs'</span>);
    <span class="keyword">end</span>
    <span class="keyword">if</span> size(u,1) == 1
        u = u';
    <span class="keyword">end</span>
<span class="keyword">end</span>

<span class="keyword">if</span> nargin &lt; 6
    u = [];
<span class="keyword">end</span>
<span class="keyword">if</span> nargin &lt; 5
    l = [];
<span class="keyword">end</span>


<span class="comment">% verifying that there is a directed path between any pair of cells in at</span>
<span class="comment">% least one of the 2 graphs</span>

paths_H = adj_H;
paths_V = adj_V;
temp_H = adj_H^2;
temp_V = adj_V^2;
<span class="keyword">while</span> (sum(temp_H(:))&gt;0)
    paths_H = paths_H + temp_H;
    temp_H = temp_H*adj_H;
<span class="keyword">end</span>
<span class="keyword">while</span> (sum(temp_V(:))&gt;0)
    paths_V = paths_V + temp_V;
    temp_V = temp_V*adj_V;
<span class="keyword">end</span>

hh = paths_H + paths_H';
vv = paths_V + paths_V';
p = hh+vv+eye(n);
all_paths = p&gt;0;
<span class="keyword">if</span> sum(all_paths(:)) ~= n^2
    error(<span class="string">'There must be a directed graph between every pair of cells in one or the other input graphs'</span>);
<span class="keyword">end</span>

par_H = sum(adj_H,2);               <span class="comment">% number of parents of each node in H</span>
par_V = sum(adj_V,2);               <span class="comment">% number of parents of each node in V</span>
chi_H = sum(adj_H);                 <span class="comment">% number of children of each node in H</span>
chi_V = sum(adj_V);                 <span class="comment">% number of children of each node in V</span>

<span class="comment">% find the root(s) for each tree</span>
roots_H = find(par_H==0);
roots_V = find(par_V==0);

<span class="comment">% find all non-root nodes for each tree</span>
nodes_H = find(par_H&gt;0);
nodes_V = find(par_V&gt;0);

<span class="comment">% find leaf(s) for each tree</span>
leafs_H = find(chi_H==0);
leafs_V = find(chi_V==0);

cvx_begin <span class="string">quiet</span>
        variables <span class="string">x(n)</span> <span class="string">y(n)</span> <span class="string">w(n)</span> <span class="string">h(n)</span> <span class="string">W</span> <span class="string">H</span>
        minimize ( W + H )
        w &gt;= 0;
        h &gt;= 0;
        x(leafs_H) &gt;= rho;
        y(leafs_V) &gt;= rho;
        x(roots_H) + w(roots_H) + rho &lt;= W;
        y(roots_V) + h(roots_V) + rho &lt;= H;
        <span class="keyword">for</span> i=1:length(nodes_H)
            node = nodes_H(i);
            c = adj_H(node,:);
            prnt = find(c&gt;0)';
            m = length(prnt);
            x(node) + w(node) + rho &lt;= x(prnt);
        <span class="keyword">end</span>

        <span class="keyword">for</span> i=1:length(nodes_V)
            node = nodes_V(i);
            c = adj_V(node,:);
            prnt = find(c&gt;0)';
            m = length(prnt);
            y(node) + h(node) + rho &lt;= y(prnt);
        <span class="keyword">end</span>

        <span class="keyword">if</span> sum(size(u))~= 0
            h &lt;= u.*w;
        <span class="keyword">end</span>
        <span class="keyword">if</span> sum(size(l))~= 0
            h &gt;= l.*w;
        <span class="keyword">end</span>
        w' &gt;= quad_over_lin([Amin.^.5;zeros(1,n)],h');
cvx_end
</pre>
</div>
</body>
</html>